import random

def is_possible(matrix, without: list[int]) -> bool:
    indices = list(matrix.keys())
    if not indices:
        return False
    if len(indices) == 1:
        return True if set(matrix[indices[0]]).difference(set(without)) else False
    else:
        for depth in matrix[indices[0]]:
            if depth not in without:
                new_matrix = matrix.copy()
                new_matrix.pop(indices[0])
                new_without = without.copy()
                new_without.append(depth)
                if is_possible(new_matrix, new_without):
                    return True
        return False
    
def induce(depths: dict, chain: list[int]) -> bool:
    updated = False

    matrix = {}
    for node in chain:
        matrix[node] = depths[node]
    for node in chain:
        if len(depths[node]) == 1:
            continue
        for depth in depths[node]:
            new_matrix = matrix.copy()
            new_matrix.pop(node)
            without = [depth]
            if not is_possible(new_matrix, without):
                depths[node].remove(depth)
                updated = True
    
    return updated

def update_depths(depths: dict, node: int, constraint: str, value: int) -> bool:
    updated = False
    if constraint == "=":
        if depths[node] != [value]:
            depths[node] = [value]
            updated = True
    elif constraint == "<=":
        for depth in depths[node].copy():
            if depth > value:
                depths[node].remove(depth)
                updated = True
    elif constraint == ">":
        for depth in depths[node].copy():
            if depth <= value:
                depths[node].remove(depth)
                updated = True
    return updated

def update(chains, depths, parents):
    while True:
        updated = False
        # 探索单链
        for k in chains.keys():
            # 末节点的深度确定了
            if update_depths(depths, k, "=", len(chains[k])):
                updated = True
            # 缩小其余节点的取值范围
            max_depth = depths[k][0] - 1
            for node in chains[k]:
                if node != k and update_depths(depths, node, "<=", max_depth):
                    updated = True
            # 进一步推理
            if induce(depths, chains[k]):
                updated = True
            # 若该链已经全部明了，则添加父子关系
            if len(chains[k]) == sum([len(depths[i]) for i in chains[k]]):
                parent = None
                son = None
                for i in range(len(chains[k])):
                    for node in chains[k]:
                        if depths[node][0] == i + 1:
                            son = node
                            parents[son] = parent
                            parent = son
                
        # 探索一对链
        ks = list(chains.keys())
        for i1, k1 in enumerate(ks[:-1]):
            for k2 in ks[i1+1:]:
                # 找交集，交集中的节点深度<=交集长度，交集外的节点深度>交集长度
                intersect = set(chains[k1]).intersection(set(chains[k2]))
                union = set(chains[k1]).union(set(chains[k1]))
                length = len(intersect)
                for node in intersect:
                    if update_depths(depths, node, "<=", length):
                        updated = True
                for node in union.difference(intersect):
                    if update_depths(depths, node, ">", length):
                        updated = True
        if not updated:
            break